/**
* MinimaxTree.java
* @author J.T. Gralka <gralkajt@washjeff.edu>, Topher Witt <wittcm19@uww.edu>
* @version 06/16/11
*
* Represents the Minimax tree structure.
*/

public class MinimaxTree{
	// ivars
	private MinimaxNode root;

	// Constructors
	public MinimaxTree(){
		root = new MinimaxNode();
	}

	public MinimaxTree(String inputString){
		MinimaxTreeParser parser = new MinimaxTreeParser(inputString);
		MinimaxTree tree = parser.getTree();
		root = tree.getRoot();
	}
	
	public MinimaxTree(MinimaxNode root){
		this.root = root;
	}

	// Accessors
	private MinimaxNode getRoot(){
		return root;
	}

	// Mutators
	public void setRoot(MinimaxNode root){
		this.root = root;
	}

	// Helper methods
	public void updateNodeTypes(boolean isMax){
		root.setIsMax(isMax); // Set the root's type
		updateNodeTypes(root); // Traverse through the rest of the tree nodes
	}
	
	private void updateNodeTypes(MinimaxNode parent){
		// For every child node of the parent...
		for(int i = 0; i < parent.getChildren().size(); i++){
			MinimaxNode temp = parent.getChildren().get(i);
			temp.setIsMax(!parent.isMax()); // Toggle the node type
			if(!temp.isLeaf()){// If the node is a not leaf...
				updateNodeTypes(temp); // Recurse for all of the subtrees
			}
		}
	}
	
	
	public MinimaxNode depthFirstSearch(MinimaxNode target){
		return depthFirstSearch(root, target);
	}

	public MinimaxNode depthFirstSearch(MinimaxNode current, MinimaxNode target){
		MinimaxNode rtn = new MinimaxNode();		
		if(current == target)
			rtn = current;
		else{
			for(current = root; current.getNext() != null; current = current.getNext()){
				return depthFirstSearch(current, target);
			}
		}
		return rtn;
	}
	
	public MinimaxNode minimaxDecision(MinimaxNode node){
		int bestIndex = 0;
		for(int i = 0; i < node.getChildren().size(); i++){
			bestIndex = node.isMax()?Math.max(bestIndex, node.getChildren().get(i).getValue()) :
					Math.min(bestIndex, node.getChildren().get(i).getValue());
		}
		return node.getChildren().get(bestIndex);
	}
	
	public static int getMaxValue(MinimaxNode state){
		if(state.isLeaf())
			return state.getValue();
		int v = Integer.MIN_VALUE;
		for(int i = 0; i < state.getChildren().size(); i++){
			MinimaxNode temp = state.getChildren().get(i);
			v = Math.max(v, getMinValue(temp));
			temp.setValue(v);
		}
		return v;
	}
	
	public static int getMinValue(MinimaxNode state){
		if(state.isLeaf())
			return state.getValue();
		int v = Integer.MAX_VALUE;
		for(int i = 0; i < state.getChildren().size(); i++){
			MinimaxNode temp = state.getChildren().get(i);
			v = Math.min(v, getMaxValue(temp));
			temp.setValue(v);
		}
		return v;
	}
	
	public void addChild(MinimaxNode parent, MinimaxNode newChild){
		parent.getChildren().add(newChild);
	}
	
	// Temporary main method
	
	public static void main(String[] arg){
		MinimaxTree tree = new MinimaxTree("#2#2#3$6#2$3#1$4$0$5#3$2$8#2$3$1");
		int val = getMaxValue(tree.getRoot());
		System.out.println(val);
		
	}
}
